package com.smh;

import org.junit.jupiter.api.Test;

import java.util.List;

/**
 * @author shiminghui
 * @date 2025/3/14 20:36
 * @description: TODO
 */
public class _045_图_bellman_ford {

    @Test
    public void test1() {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        Vertex v7 = new Vertex("v7");
        Vertex v8 = new Vertex("v8");
        Vertex v9 = new Vertex("v9");
        Vertex v10 = new Vertex("v10");

        // 设置边
        v1.setEdges(List.of(
                new Edge(v1, v2, 4),
                new Edge(v1, v3, -2),
                new Edge(v1, v4, 7)
        ));
        v2.setEdges(List.of(
                new Edge(v2, v5, 3),
                new Edge(v2, v6, 8)
        ));
        v3.setEdges(List.of(
                new Edge(v3, v4, 1),
                new Edge(v3, v7, 6)
        ));
        v4.setEdges(List.of(
                new Edge(v4, v8, 5)
        ));
        v5.setEdges(List.of(
                new Edge(v5, v9, 2)
        ));
        v6.setEdges(List.of(
                new Edge(v6, v10, 4)
        ));
        v7.setEdges(List.of(
                new Edge(v7, v8, 3),
                new Edge(v7, v10, 7)
        ));
        v8.setEdges(List.of(
                new Edge(v8, v9, 1)
        ));
        v9.setEdges(List.of(
                new Edge(v9, v10, 2)
        ));
        v10.setEdges(List.of(
                new Edge(v10, v1, 1) // 构造环路
        ));

        // 调用迪杰斯特拉算法
        bellmanFord(List.of(v1, v2, v3, v4, v5, v6, v7, v8, v9, v10), v1);
    }

    /**
     * Bellman-Ford算法, 用于解决负权边的最短路径问题
     * 使用了动态规划的思想,每次都会遍历一次所有边，如果发现更短的路径，则更新，
     * 只不过他将缓存信息存储到了对象的一个属性里面,而不是一维或二维数组中
     * 递推公式是 d[v] = min(d[v], d[u] + w(u, v))
     * @param vertexs
     * @param v
     */
    public void bellmanFord(List<Vertex> vertexs, Vertex v) {
        int size = vertexs.size();
        v.setDistance(0);
        for (int i = 0; i <= size; i++) {
            for (Vertex vertex : vertexs) {
                List<Edge> edges = vertex.getEdges();
                if (edges == null) {
                    continue;
                }
                for (Edge edge : edges) {
                    Vertex edgeTo = edge.getTo();
                    int newDist = vertex.getDistance() + edge.getWeight();
                    if (newDist < edgeTo.getDistance()) {
                        if (i == size) {
                            System.out.println("存在负环");
                            return;
                        }
                        edgeTo.setDistance(newDist);
                        edgeTo.setPre(vertex);
                    }
                }
            }
        }
        for (Vertex vertex : vertexs) {
            System.out.print(vertex.getName() + "到" + v.getName() + "的最短路径为：" + vertex.getDistance() + "," + vertex.getName());
            while (vertex.getPre() != null) {
                System.out.print(" <- " + vertex.getPre().getName());
                vertex = vertex.getPre();
            }
            System.out.println();
        }

    }


    private class Vertex {
        private String name;
        private int status;
        private List<Edge> edges;
        private int inDegree; // 入度
        private boolean isVisited; // 是否访问过
        private int distance; // 到该顶点的最短路径
        private Vertex pre; // 记录该顶点的前驱顶点

        { // 初始化
            status = 0;
            distance = Integer.MAX_VALUE;
            isVisited = false;
            inDegree = 0;
        }

        public Vertex(String name) {
            this.name = name;
        }

        public Vertex(String name, List<Edge> edges) {
            this.name = name;
            this.edges = edges;
        }

        public Vertex getPre() {
            return pre;
        }

        public void setPre(Vertex pre) {
            this.pre = pre;
        }

        public boolean isVisited() {
            return isVisited;
        }

        public void setVisited(boolean visited) {
            isVisited = visited;
        }

        public int getDistance() {
            return distance;
        }

        public void setDistance(int distance) {
            this.distance = distance;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getStatus() {
            return status;
        }

        public void setStatus(int status) {
            this.status = status;
        }

        public List<Edge> getEdges() {
            return edges;
        }

        public void setEdges(List<Edge> edges) {
            this.edges = edges;
        }

        public int getInDegree() {
            return inDegree;
        }

        public void setInDegree(int inDegree) {
            this.inDegree = inDegree;
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "name='" + name + '\'' +
                    '}';
        }
    }

    private class Edge {
        private Vertex from;
        private Vertex to;
        private int weight;

        public Edge(Vertex from, Vertex to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public Vertex getFrom() {
            return from;
        }

        public void setFrom(Vertex from) {
            this.from = from;
        }

        public Vertex getTo() {
            return to;
        }

        public void setTo(Vertex to) {
            this.to = to;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }
}
